package main

import (
	"fmt"
	"strings"
)

// leetcode basic calculator 1 + 2 + 3
//给输入为string，例如"2+3-999"，之包含+-操作，返回计算结果。

func basicCalculator1(expression string) int {
	res := 0
	expression = strings.ReplaceAll(expression, " ", "")
	sign := 1
	for i := 0; i < len(expression); i++ {
		if expression[i] >= '0' && expression[i] <= '9' {
			// number
			num := 0
			j := i
			for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
				num = num*10 + int(expression[j]-'0')
				j++
			}
			res = res + sign*num
			i = j - 1
		} else {
			// symbol
			if expression[i] == '-' {
				sign = -1
			} else {
				sign = 1
			}
		}
	}
	// res := 0
	// sign := 1 // 1 positive, -1 negative
	// // stack := []int{}
	// expression = strings.ReplaceAll(expression, " ", "")

	// for index := 0; index < len(expression); index++ {
	// 	// is number?
	// 	if expression[index] >= '0' && expression[index] <= '9' {
	// 		num := 0
	// 		i := index
	// 		for i < len(expression) && expression[i] >= '0' && expression[i] <= '9' {
	// 			num = num*10 + int(expression[i]-'0')
	// 			i++
	// 		}
	// 		index = i - 1

	// 		res = res + sign*num
	// 	} else {
	// 		// operation or parentheses
	// 		if expression[index] == '-' {
	// 			sign = -1
	// 		} else if expression[index] == '+' {
	// 			sign = 1
	// 		}
	// 	}
	// }
	return res
}

func basicCalculator2(expression string) int {
	res := 0
	sign := 1 // 1 positive, -1 negative
	expression = strings.ReplaceAll(expression, " ", "")

	for i := 0; i < len(expression); i++ {
		if expression[i] >= '0' && expression[i] <= '9' {
			// number
			num := 0
			j := i
			for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
				value := int(expression[j] - '0')
				num = num*10 + value
				j++
			}

			res = res + sign*num
			i = j - 1
		} else {
			if expression[i] == '-' {
				sign = -1
			} else if expression[i] == '+' {
				sign = 1
			} else if expression[i] == '(' {
				// find the matching )
				pCount := 1
				j := i + 1
				for j < len(expression) && pCount != 0 {
					if expression[j] == '(' {
						pCount++
					}
					if expression[j] == ')' {
						pCount--
					}
					j++
				}
				substring := expression[i+1 : j-1]
				subVAlue := basicCalculator2(substring)
				res = res + sign*subVAlue
				i = j - 1
			} else {
				continue
			}
		}
	}

	// i := 0
	// for i < len(expression) {
	// 	if expression[i] >= '0' && expression[i] <= '9' {
	// 		num := 0
	// 		j := i
	// 		for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
	// 			num = num*10 + int(expression[j]-'0')
	// 			j++
	// 		}
	// 		res = res + sign*num
	// 		i = j - 1
	// 	} else if expression[i] == '(' {
	// 		// find the next valid matching )
	// 		j := i + 1
	// 		cnt := 1
	// 		for j < len(expression) && cnt != 0 {
	// 			if expression[j] == '(' {
	// 				cnt++
	// 			}
	// 			if expression[j] == ')' {
	// 				cnt--
	// 			}
	// 			j++
	// 		}
	// 		substr := expression[i+1 : j-1]
	// 		subNum := basicCalculator2(substr)
	// 		res = res + sign*subNum
	// 		i = j - 1
	// 	} else {
	// 		if expression[i] == '-' {
	// 			sign = -1
	// 		} else if expression[i] == '+' {
	// 			sign = 1
	// 		}
	// 	}
	// 	i++
	// }
	return res
}

func basicCalculate3(expression string) int {
	num := 0
	sign := 1 // 1 positive, -1 negative
	stack := []int{}
	expression = strings.ReplaceAll(expression, " ", "")

	for i := 0; i < len(expression); i++ {
		if expression[i] >= '0' && expression[i] <= '9' {
			// number
			j := i
			num = 0
			for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
				num = num*10 + int(expression[j]-'0')
				j++
			}
			stack = append(stack, sign*num)
			num = 0
			i = j - 1
		} else if expression[i] == '(' {
			// find the next valid matching )
			j := i + 1
			cnt := 1
			for j < len(expression) && cnt != 0 {
				if expression[j] == '(' {
					cnt++
				}
				if expression[j] == ')' {
					cnt--
				}
				j++
			}
			substr := expression[i+1 : j-1]
			subNum := calculate3(substr)
			// fmt.Println(subNum)
			stack = append(stack, sign*subNum)
			i = j - 1
		} else {
			//operator

			switch expression[i] {
			case '-':
				sign = -1
			case '+':
				sign = 1
			case '*':
				number1 := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				// find number 2
				j := i + 1
				number2 := 0
				for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
					number2 = number2*10 + int(expression[j]-'0')
					j++
				}
				stack = append(stack, number1*number2)
				i = j - 1
			case '/':
				number1 := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				// find number 2
				j := i + 1
				number2 := 0
				for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
					number2 = number2*10 + int(expression[j]-'0')
					j++
				}
				stack = append(stack, number1/number2)
				i = j - 1
			}
		}
	}
	if num != 0 {
		stack = append(stack, num)
	}
	// fmt.Println(stack)
	return sum(stack)
}

func sum(array []int) int {
	result := 0
	for _, v := range array {
		result += v
	}
	return result
}

func main() {
	// expression1_1 := "10 - 1000 + 500 + 900"
	expression1 := "-2+3-999"
	fmt.Println(basicCalculator1(expression1))
	expression2 := "-3+(40-50)+100"
	// expression2 := "(40-50)+2"
	fmt.Println(basicCalculator2(expression2))
	expression3 := "2*(5+5*2)/3+(6/2+8)"
	fmt.Println(basicCalculate3(expression3))
}
